{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## **实验八 二叉树操作实现**\n",
    "要求：采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后续以及按层次遍历操作，用后续遍历的方法求二叉树的深度、以及所有叶子节点的数目及节点总数的操作。\n",
    "画出所设计的二叉树，以后续遍历算法为例，画出执行轨迹示意图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- # %%html -->\n",
    "<img src=\"实验八.jpg\" width=\"70%\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "\n",
    "class BTree():\n",
    "\n",
    "    # 初始化\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        \n",
    "        \n",
    "        \n",
    "    # 前序遍历\n",
    "    def preorder(self):\n",
    "        if self.data is not None:\n",
    "            print(self.data,end=' ') \n",
    "        if self.left is not None:\n",
    "            self.left.preorder() \n",
    "        if self.right is not None:\n",
    "            self.right.preorder() \n",
    "    \n",
    "        # 中序遍历\n",
    "    def inorder(self):\n",
    "\n",
    "        if self.left is not None:\n",
    "            self.left.inorder()\n",
    "        if self.data is not None:\n",
    "            print(self.data, end=' ')\n",
    "        if self.right is not None:\n",
    "            self.right.inorder()\n",
    "\n",
    "    # 后序遍历\n",
    "    def postorder(self):\n",
    "\n",
    "        if self.left is not None:\n",
    "            self.left.postorder()\n",
    "        if self.right is not None:\n",
    "            self.right.postorder()\n",
    "        if self.data is not None:\n",
    "            print(self.data, end=' ')\n",
    "\n",
    "    # 层序遍历\n",
    "    def levelorder(self):\n",
    "\n",
    "        # 返回某个节点的左孩子\n",
    "        def LChild_Of_Node(node):\n",
    "            return node.left if node.left is not None else None\n",
    "        # 返回某个节点的右孩子\n",
    "        def RChild_Of_Node(node):\n",
    "            return node.right if node.right is not None else None\n",
    "\n",
    "        # 层序遍历列表\n",
    "        level_order = []\n",
    "        # 是否添加根节点中的数据\n",
    "        if self.data is not None:\n",
    "            level_order.append([self])\n",
    "\n",
    "        # 二叉树的高度\n",
    "        height = self.height()\n",
    "        if height >= 1:\n",
    "            # 对第二层及其以后的层数进行操作, 在level_order中添加节点而不是数据\n",
    "            for _ in range(2, height + 1):\n",
    "                level = []  # 该层的节点\n",
    "                for node in level_order[-1]:\n",
    "                    # 如果左孩子非空，则添加左孩子\n",
    "                    if LChild_Of_Node(node):\n",
    "                        level.append(LChild_Of_Node(node))\n",
    "                    # 如果右孩子非空，则添加右孩子\n",
    "                    if RChild_Of_Node(node):\n",
    "                        level.append(RChild_Of_Node(node))\n",
    "                # 如果该层非空，则添加该层\n",
    "                if level:\n",
    "                    level_order.append(level)\n",
    "\n",
    "            # 取出每层中的数据\n",
    "            for i in range(0, height):  # 层数\n",
    "                for index in range(len(level_order[i])):\n",
    "                    level_order[i][index] = level_order[i][index].data\n",
    "\n",
    "        return level_order\n",
    "              \n",
    "    def height(self):\n",
    "        if self.data is None:\n",
    "            return 0 \n",
    "        elif self.left is None and self.right is None:\n",
    "            return 1\n",
    "        elif self.left is None and self.right is not None:\n",
    "            return 1 + self.right.height()\n",
    "        elif self.left is not None and self.right is None:\n",
    "            return 1 + self.left.height()\n",
    "        else:\n",
    "            return 1 + max(self.left.height(),self.right.height())\n",
    "        \n",
    "    def leaves(self):\n",
    "        \n",
    "        if self.data is None:\n",
    "            return None\n",
    "        elif self.left is None and self.right is None:\n",
    "            print(self.data,end=' ')\n",
    "        elif self.left is None and self.right is not None:\n",
    "            self.right.leaves()\n",
    "        elif self.left is not None and self.right is None:\n",
    "            self.left.leaves()\n",
    "        else:\n",
    "            self.left.leaves()\n",
    "            self.right.leaves()\n",
    "    def numberofNodes(self):\n",
    "\n",
    "        nodes = 1 + numberofNodes(self.left) + numberofNodes(self.right)\n",
    "        return nodes\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 先序输入创建二叉树\n",
    "\n",
    "def preCreat(s):\n",
    "    \n",
    "    if len(s) == 0:\n",
    "        return None\n",
    "    char_cur = s.pop(0)\n",
    "    if char_cur=='#':\n",
    "        return None\n",
    "    else:\n",
    "        root = BTree(char_cur)\n",
    "        root.left = preCreat(s)\n",
    "        root.right = preCreat(s)\n",
    "\n",
    "        return root\n",
    "    \n",
    "# 节点总数\n",
    "def numberofNodes(tree):\n",
    "    if not tree:\n",
    "        return 0\n",
    "    else:\n",
    "        nodes = 1 + numberofNodes(tree.left) + numberofNodes(tree.right)\n",
    "    return nodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 先序输入'ABC##DE#G##F###'创建二叉树"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = 'ABC##DE#G##F###'\n",
    "tree = preCreat(list(s))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 二叉树遍历"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "先序遍历：\n",
      "A B C D E G F \n",
      "中序遍历：\n",
      "C B E G D F A \n",
      "后序遍历：\n",
      "C G E F D B A \n",
      "层序遍历：\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[['A'], ['B'], ['C', 'D'], ['E', 'F'], ['G']]"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 先序遍历\n",
    "print('先序遍历：')\n",
    "tree.preorder()\n",
    "# 中序遍历\n",
    "print('\\n中序遍历：')\n",
    "tree.inorder()\n",
    "# 后序遍历\n",
    "print('\\n后序遍历：')\n",
    "tree.postorder()\n",
    "# 层序遍历\n",
    "print('\\n层序遍历：')\n",
    "tree.levelorder()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 深度、所有叶子及节点总数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "深度: 5 \n",
      "叶子节节点： C G F \n",
      "节点总数为： 7\n"
     ]
    }
   ],
   "source": [
    "print ('深度:',tree.height(),end = ' ')\n",
    "print('\\n叶子节节点：',end = ' ')\n",
    "tree.leaves()\n",
    "print('\\n节点总数为：',tree.numberofNodes())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<__main__.TreeNode object at 0x000001D32FC01FC8>\n",
      "1 2 4 6 5 7 3 8 9 "
     ]
    }
   ],
   "source": [
    "class TreeNode(object):\n",
    "    def __init__(self,value):\n",
    "        self.value=value\n",
    "        self.leftnode=None\n",
    "        self.rightnode=None\n",
    "    \n",
    "        # 前序遍历\n",
    "    def preorder(self):\n",
    "        if self.value is not None:\n",
    "            print(self.value,end=' ') \n",
    "        if self.leftnode is not None:\n",
    "            self.leftnode.preorder() \n",
    "        if self.rightnode is not None:\n",
    "            self.rightnode.preorder() \n",
    "str_raw='1246###5#73#89##'\n",
    "def deserialize(chars):\n",
    "    if len(chars)==0:\n",
    "        return None\n",
    "    assert isinstance(chars,list)\n",
    "    char_cur=chars.pop(0)\n",
    "    if char_cur=='#':\n",
    "        return None\n",
    "    else:\n",
    "        node_cur=TreeNode(char_cur)\n",
    "        node_cur.leftnode=deserialize(chars)\n",
    "        node_cur.rightnode=deserialize(chars)\n",
    "        return node_cur\n",
    "\n",
    "out=deserialize(list(str_raw))\n",
    "print(out)\n",
    "deserialize(list(str_raw)).preorder()\n",
    "\n",
    "# str_out=''\n",
    "# def serialization(tree_in):\n",
    "#     global str_out\n",
    "#     str_out=str_out+tree_in.value\n",
    "#     if tree_in.leftnode:\n",
    "#         serialization(tree_in.leftnode)\n",
    "#     else:\n",
    "#         str_out+='#'\n",
    "#     if tree_in.rightnode:\n",
    "#         serialization(tree_in.rightnode)\n",
    "#     else:\n",
    "#         str_out+='#'\n",
    "# serialization(out)\n",
    "# print(str_out)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## **实验九线索二叉树的实现**\n",
    "要求：采用线索二叉树链表作为存储结构，完成二叉树的建立，对二叉树进行中序线索化，并进行中序遍历。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- # %%html -->\n",
    "<img src=\"实验九.jpg\" width=\"70%\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
